/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.string;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * <p>
 * 恢复IP地址
 * Given "25525511135",
 * return ["255.255.11.135", "255.255.111.35"].
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月14日
 */
public class RestoreIPAddresses {

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        String ip = "";
        restoreIpAddresses(s, 0 , 0,ip,result);
        return result;
    }

    /**
     * @param s
     * @param start
     * @param part
     * @param ip
     * @param result
     * @author towan
     * 2015年6月14日
     */
    private void restoreIpAddresses(String s, int start, int part, String ip, List<String> result) {
      //数字过多，则忽略
        if(s.length()-start>(4-part)*3){
            return;
        }
        //忽略剩余数字过少情况
        if(s.length()-start<(4-part)){
            return;
        }
        //找出一个合法的ip
        if(start==s.length() && part==4){
            //把最后一个点号去掉
            result.add(ip.substring(0,ip.length()-1));
            return;
        }
        int num = 0;
        for(int i=start;i<Math.min(start+3, s.length());i++){
            //每个位置有三种可能
            num = num*10+(s.charAt(i)-'0');
            if(num<=255){
                //每段数字小于256
                ip = ip+s.charAt(i);
                restoreIpAddresses(s,i+1,part+1,ip+".",result);
            }
            if(num==0){
                break;
            }
        }
    }
    @Test
    public void test2(){
        String ip = "25525511135";
        System.out.println(restoreIpAddresses(ip));
        
    }
}
